\documentclass{article}
% ========================
% = document information =
% ========================
\title{An Overview of Two Approaches for Knowledge Representation and Reasoning in the Context of Planning}
\author{Gregory Gelfond and Glen Hunt}
\date{\today}

% =================================
% various useful packages
% =================================

\usepackage{listings}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{ccfonts}
\usepackage{euler}
\usepackage{graphicx}
\usepackage[T1]{fontenc}
\usepackage[scaled]{beramono}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage[parfill]{parskip}
\usepackage[usenames,dvipsnames]{color}
\usepackage[top=1in,bottom=1in,left=1in,right=1in,includehead,includefoot,letterpaper]{geometry}
\usepackage{tabularx}
\usepackage{booktabs}

% ==========
% = colors =
% ==========
\definecolor{LightGray}{gray}{.5}
\definecolor{LighterGray}{gray}{.75}
\definecolor{IdentifierGray}{gray}{.2}

% ======================
% = listing appearance =
% ======================
\lstset{
basicstyle=\footnotesize\ttfamily,
keywordstyle=\color{MidnightBlue},
commentstyle=\color{LightGray}\itshape,
stringstyle=\color{OliveGreen},
emph={True,False,None},
emphstyle=\color{RedOrange},
identifierstyle=\color{IdentifierGray},
numbers=left,
numberstyle=\tiny\ttfamily\color{LighterGray},
numbersep=10px,
breaklines=true,
breakatwhitespace=true,
showstringspaces=false,
frame=single
}

% =================================
% mathematical notation
% =================================

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{example}{Example}
\newtheorem{definition}{Definition}
\newtheorem{observation}{Observation}
\newtheorem{corollary}{Corollary}


\newcommand{\pair}[2]{\ensuremath{(#1, #2)}}
\newcommand{\triple}[3]{\ensuremath{(#1, #2, #3)}}
\newcommand{\union}{\ensuremath{\cup}}
\newcommand{\intersection}{\ensuremath{\cap}}
\newcommand{\conj}{\ensuremath{\wedge}}
\newcommand{\disj}{\ensuremath{\vee}}
\newcommand{\impl}{\ensuremath{\Rightarrow}}
\newcommand{\eqvl}{\ensuremath{\Leftrightarrow}}
\newcommand{\entails}{\ensuremath{\models}}
\newcommand{\ktimes}{\ensuremath{\otimes}}
\newcommand{\AL}{\ensuremath{\mathcal{AL}}}

% =================================
% action language notation
% =================================

\newcommand{\dynamiclaw}[2]{\ensuremath{#1 \: \mathbf{causes} \: #2}}
\newcommand{\dynamiclawp}[3]{\ensuremath{#1 \: \mathbf{causes} \: #2 \: \mathbf{if} \: #3}}
\newcommand{\staticlaw}[2]{\ensuremath{#1 \: \mathbf{if} \: #2}}
\newcommand{\initially}[1]{\ensuremath{\mathbf{initially} \: #1}}
\newcommand{\impossible}[2]{\ensuremath{\mathbf{impossible} \: #1 \: \mathbf{if} \: #2}}
\newcommand{\sense}[2]{\ensuremath{#1 \: \mathbf{determines} \: #2}}
\newcommand{\maysense}[2]{\ensuremath{#1 \: \mathbf{may \: determine} \: #2}}
\newcommand{\announce}[2]{\ensuremath{#1 \: \mathbf{announces} \: #2}}
\newcommand{\observes}[3]{\ensuremath{#1 \: \mathbf{observes} \: #2 \: \mathbf{if} \: #3}}
\newcommand{\observesu}[2]{\ensuremath{#1 \: \mathbf{observes} \: #2}}
\newcommand{\observesp}[3]{\ensuremath{#1 \: \mathbf{partially \: observes} \: #2 \: \mathbf{if} \: #3}}

% =====================================
% = bold font fix when using concrete =
% =====================================
\renewcommand{\bfdefault}{sbc}

\begin{document}
\maketitle
\tableofcontents
\pagebreak

\section{Introduction}

Dijkstra viewed programming as the process of the ``refinement of specification.'' This applies not only to imperative programming, but in the myriad fields of Artificial Intelligence Research. It is especially made clear given that the levels of refinement we are able to obtain in our various formalisms, programs, etc.\, are inherently tied to the languages we use to reason about our problem domains.

This is also a central view taken by many members of what has been termed: the ``Knowledge Representation and Reasoning Community.'' Within this community one of the central goals has been to understand and formalize the reasoning of intelligent agents. A number of languages have developed such \emph{action languages}, and the language of \emph{answer set prolog} (denoted throughout as A-Prolog). A rather significant body of work has been done regarding various reasoning tasks such as planning, diagnosis, prediction, counter-factual reasoning, etc., all from the perspective of them being simply one of many reasoning tasks an agent may perform. This has lead to a framework for the design and development of intelligent agents based on a \emph{portfolio} of languages, corresponding roughly to individual levels of refinement about an agent's knowledge of the domain.

This central view does not appear to be shared by the ``Classical Planning'' community, given its use of a single language, \emph{PDDL}, which was ``originally developed by the AIPS-98 Competition Committee for use in defining problem domains.''

This difference in first principles leads to some interesting consequences which we hope to explore to some extent in this paper. The rest of this paper is structured as follows: an overview of the classical planning approach will be given in the context of four different planning domains, The Blocks World, Towers of Hanoi, Lin's Briefcase, and an Electrical Circuit. Once this has been, a similar overview of the knowledge representation and reasoning approaches, including descriptions of the action language $\AL$, followed by the logic programming language of A-Prolog. Once this has been covered, representations of the aforementioned domains will be presented.

\section{Classical Planning Overview}
\subsection{Background}
\input{../classical_planning/background}

\subsection{PDDL}
\input{../classical_planning/pddl}

\subsection{FF Planner}
\input{../classical_planning/ff}

\subsection{Planning Domain Examples}\label{sub:planning_domain_examples}
\input{../classical_planning/domains}

\section{The Knowledge Representation and Reasoning Approach}

As was stated earlier, in the knowledge representation and reasoning community, the general approach is centered around the use of a portfolio of various knowledge representation languages, among which are the action language $\AL$, and the logic programming language A-Prolog. In keeping with the notion of programming as the refinement of specification we:
\begin{enumerate}
    \item Construct a mental model of the transition system described by the domain
    \item Describe the transition system via an \emph{action description} in some action language (such as $\AL$)
    \item Refine the action description further by translation into A-Prolog
\end{enumerate}
In this section we take a brief look at the languages $\AL$ and A-Prolog, and show their application towards the aforementioned domains.

\subsection{The Action Language $\AL$}

Simply put, action languages are a family of declarative languages designed for the purpose of describing the effects of actions. They have a simple syntax and semantics, while remaining powerful enough to represent many complex reasoning domains \cite{Bald2005}. Collections of statements are called \emph{action descriptions}, and define transitions whose nodes correspond to \emph{possible states of the world}\footnote{A difference we believe to be significant from the conception of a state in the classical view as simply an interpretation of the fluents present in a domain.}, and whose arcs are labeled by actions. An arc $\triple{\sigma}{\alpha}{\tau}$ states that if action $\alpha$ occurs in state $\sigma$, the resulting state will be $\tau$. In addition to specifying what changes due to the occurrence of a particular action, it is also vital to be able to specify what does not change. This is know as the \emph{frame problem} \cite{Shan97}, and its solution lies in an elegant and precise representation of what is called the \emph{inertia axiom}. The beauty and utility of such languages stems from the ability to compactly represent huge transition systems, and in their graceful approach towards solving the frame problem.

Action descriptions in the language of $\AL$ are collections of three statement types: \emph{dynamic causal laws}, \emph{static causal laws}, and \emph{impossibility conditions}. Dynamic causal laws are statements of the form:
\begin{align*}
    &\dynamiclawp{a}{f}{l_{0},\ldots,l_{n}}
\end{align*}
where $a$ is an action, and $f$, and $l_{0},\ldots,l_{n}$ are fluent literals. Laws of this form a read as: ``action $a$ causes $f$ to be come true if $l_{0},\ldots,l_{n}$.'' The corresponding arc in the transition diagram is shown in Figure~\ref{fig-dcl}.
\begin{figure}[htb]
    \centering
    \includegraphics[scale=0.5]{dynamic-law}
    \caption{transition defined by a simple causal law}
    \label{fig-dcl}
\end{figure}

Static causal laws have the form:
\begin{align*}
    &\staticlaw{f}{l_{0},\ldots,l_{n}}
\end{align*}
where $f$, and $l_{0},\ldots,l_{n}$ are fluent literals. Such laws are read as: ``$f$ is true whenever $l_{0},\ldots,l_{n}$ are true.'' Unlike dynamic causal laws, static laws are used to describe the properties of states, as well as the \emph{indirect effects} of actions.
\begin{example}
{\rm
Consider the following action description $AD_{1}$:
\begin{align*}
    &\dynamiclaw{a}{f} \\
    &\staticlaw{g}{f}
\end{align*}
and let the state, $\sigma = \{\neg{f}, \neg{g}\}$. If $a$ is executed in $\sigma$, we have the transition depicted in Figure~\ref{fig-scl}.
\begin{figure}[htb]
    \centering
    \includegraphics[scale=0.5]{static-law}
    \caption{transition involving both direct and indirect effects}
    \label{fig-scl}
\end{figure}
}
\end{example}

Impossibility conditions have the form:
\begin{align*}
    &\impossible{a}{l_{0},\ldots,l_{n}}
\end{align*}
where as before, $a$ is an action, and $l_{0},\ldots,l_{n}$ are fluent literals. Rules such as this are used to state that: ``action $a$ may not occur in a state which satisfies $l_{0},\ldots,l_{n}$.'' From the view of a transition system, this means that there are no outgoing arcs labeled by $a$ originating from a state which satisfies $l_{0},\ldots,l_{n}$.

The semantics of an action description of $\AL$ is given by its transition diagram. For a more detailed treatment, we refer the reader to \cite{Bald2005}. Having described the action language $\AL$, we now turn our attention to the language of A-Prolog.

\subsection{The Language of A-Prolog}

The language of A-Prolog is a logic programming language developed by Michael Gelfond and Vladimir Lifschitz in \cite{GL88}. It has a simple syntax, and is focused on modeling the beliefs of a rational agent. A rather broad community has developed around it, and it has emerged as strong programming paradigm in its own right.

A logic program in the language of A-Prolog is defined as a collection of rules of the form \cite{GL88,Baral03}:
\begin{align*}
    &l_{0} \leftarrow l_{1},\ldots,l_{m}, not \: l_{m+1}, \ldots, not \: l_{n}.
\end{align*}
where $0 \leq m \leq n$, each $l_{i}$ is a literal, and $not$ represents \emph{negation-as-failure} (also termed \emph{default negation}). Rules of this form are read as: ``if an agent believes $l_{1},\ldots,l_{m}$ to be true and has no reason to believe in $l_{m+1},\ldots,l_{n}$, then he believes $l_{0}$ to be true.''

The left-hand side of a rule is known as the \emph{head}, and the right-hand side is called the \emph{body}. Rules with empty heads are known as \emph{constraints}, while those with empty bodies are termed \emph{facts}.

The variables of a program $\Pi$ range over the set of ground terms of its signature $\sigma$. Programs which do not contain any variables are said to be \emph{ground}. A rule $r$ which does contain variables may be viewed as a shorthand form for the entire set of its ground instantiations. A \emph{definite rule} is a rule which does not contain any occurrences of default negation, and programs comprised solely of definite rules are called \emph{definite programs}.

Let $S$ be a set of ground literals. The body of a rule is satisfied by $S$ if $\{l_{m+1},\ldots,l_{n}\} \intersection S = \emptyset$ and $\{l_{1},\ldots,l_{m}\} \subseteq S$. A rule with a non-empty head is satisfied by $S$ if either its body is not satisfied by $S$ or $l_{0} \in S$. A constraint is satisfied by $S$ if its body is not satisfied by $S$.

Given an arbitrary program $\Pi$, and a set of ground literals, $S$, the \emph{reduct} of $\Pi$ with respect to $S$, denoted by $\Pi^{S}$ is the definite program obtained from $\Pi$ by:
\begin{enumerate}
    \item deleting all rules in $\Pi$ which $not \: l$ in the body, where $l \in S$
    \item removing all remaining occurrences of $not \: l$ from the bodies of the remaining rules
\end{enumerate}
A set of ground literals, $S$, is said to be an answer set of a logic program $\Pi$ if it satisfies the following:
\begin{enumerate}
    \item if $\Pi$ is a definite program then $S$ is a minimal set of literals satisfying all of the rules of $\Pi$
    \item if $\Pi$ is not a definite program the $S$ is an answer set of $\Pi$ if and only if $S$ is an answer set of $\Pi^{S}$
\end{enumerate}

The fact that a program can have multiple (or no) answer sets has given rise to an alternative method of solving problems through logic programming, called \emph{Answer Set Programming} (ASP) \cite{Marek99,Niemela99}. In this approach, we develop logic programs whose answer sets have a one-to-one correspondence with the solutions of the particular problem being modeled. Typically an ASP program consists of:
\begin{itemize}
    \item rules for the enumeration of possible solutions to a problem as \emph{candidate answer sets}
    \item constraints which remove candidates that do not correspond to solutions of the problem
\end{itemize}
In the context of planning, the ``planning module'' will serve to generate possible sequences of while the ``goal specification'' will prune those which fail to satisfy our goal. 

\subsection{Domains}

In this section we examine a number of planning and apply the knowledge representation and reasoning approach towards their resolution. All of the listings presented in this paper are in the input language of the clingo answer set programming system \cite{clingo}.

\subsubsection{Lin's Briefcase}

Consider a domain consisting of a briefcase with two latches. Flipping a closed latch causes it to be open, while flipping an open latch causes it to become closed. How do we represent this domain using the reasoning about actions approach?

We begin by constructing a mental model of the system, which involves the transition system shown in Figure~\ref{lin-tran}.

\begin{figure}[htb]
    \centering
    \includegraphics[scale=0.50]{briefcase}
    \caption{transition system for the Lin's Briefcase domain}
    \label{lin-tran}
\end{figure}

Once we have the transition fixed, we represent in in $\AL$ as follows:
\begin{align*}
    &\dynamiclawp{flip(l_{1})}{open(l_{1})}{\neg{open(l_{1})}} \\
    &\dynamiclawp{flip(l_{1})}{\neg{open(l_{1})}}{open(l_{1})} \\
    &\dynamiclawp{flip(l_{2})}{open(l_{2})}{\neg{open(l_{2})}} \\
    &\dynamiclawp{flip(l_{2})}{\neg{open(l_{2})}}{open(l_{2})} \\
    &\staticlaw{open(b)}{open(l_{1}),\:open(l_{2})} \\
    &\staticlaw{\neg{open(b)}}{\neg{open(l_{1})}} \\
    &\staticlaw{\neg{open(b)}}{\neg{open(l_{2})}}
\end{align*}

With our domain description in place, we translate the above laws and add some additional domain related information to obtain the following A-Prolog program:

\begin{lstlisting}[language=Prolog, caption=Lin's Briefcase Domain Description in A-Prolog, label=lst:asp-briefcase]
% ============================
% OBJECTS
% ============================

#const n = 2.

time(0..n).

latch(1).
latch(2).

% ============================
% FLUENTS
% ============================

fluent(open(Latch)) :-
	latch(Latch).

fluent(opened).

% ============================
% ACTIONS
% ============================

action(flip(Latch)) :-
	latch(Latch).

% ============================
% CAUSAL LAWS
% ============================

holds(open(Latch), T + 1) :-
	occurs(flip(Latch), T),
	-holds(open(Latch), T),
	latch(Latch),
	time(T).

-holds(open(Latch), T + 1) :-
	occurs(flip(Latch), T),
	holds(open(Latch), T),
	latch(Latch),
	time(T).

-holds(opened, T) :-
	-holds(open(Latch), T),
	latch(Latch),
	time(T).

holds(opened, T) :-
	not -holds(opened, T),
	time(T).

% ============================
% INERTIA AXIOMS
% ============================

holds(Fluent, T + 1) :-
    holds(Fluent, T),
    not -holds(Fluent, T + 1),
    fluent(Fluent),
    time(T).

-holds(Fluent, T + 1) :-
    -holds(Fluent, T),
    not holds(Fluent, T + 1),
    fluent(Fluent),
    time(T).

% ============================
% INITIAL STATE
% ============================

-holds(open(Latch), 0) :-
	latch(Latch).

% ============================
% GOAL SPECIFICATION
% ============================

goal(T) :-
	holds(opened, T),
	time(T).

done :-
	goal(T).

:- not done.

% ============================
% PLANNING MODULE
% ============================

1{occurs(Action,T) : action(Action)}1 :-
    not goal(T),
    time(T).

% ============================
% SOLVER DIRECTIVES
% ============================

#hide.
#show occurs(_,_).
\end{lstlisting}

\noindent Utilizing the clingo answer set solver we obtain the following two plans (this is due to the fact that the planning module is written in such a way as to only look for sequential plans, parallel plans may be supported through a minor modification):
\begin{verbatim}
Answer: 1
occurs(flip(2),1) occurs(flip(1),0) 
Answer: 2
occurs(flip(1),1) occurs(flip(2),0) 
SATISFIABLE

Models      : 2     
Time        : 0.000
  Prepare   : 0.000
  Prepro.   : 0.000
  Solving   : 0.000
\end{verbatim}

\subsubsection{The Blocks World}

The next domain we examine is the Blocks Worlds. In this domain an agent seeks to build a tower out of a set blocks. This domain makes full use of the full range of causal laws provided for in $\AL$. For the sake of space, the $\AL$ description of the system has not been included, however, a reading of the relevant causal laws in the A-Prolog representation will show that each type of law is used and follows the same representation scheme we have seen previously with Lin's Briefcase.

\begin{lstlisting}[language=Prolog, caption=Blocks World Domain Representation in A-Prolog, label=lst:bworld-asp]
% ============================
% OBJECTS
% ============================

#const n = 3.

time(0..n).

block(a).
block(b).
block(c).
block(d).

table(t).

location(X) :- block(X).
location(X) :- table(X).

% ============================
% FLUENTS
% ============================

fluent(on(Block,Location)) :-
    Block != Location,
	block(Block),
	location(Location).

fluent(clear(Location)) :-
    location(Location).

% ============================
% ACTIONS
% ============================

action(move(Block,Location)) :-
    Block != Location,
    block(Block),
    location(Location).

% ============================
% CAUSAL LAWS
% ============================

holds(on(Block,Location), T + 1) :-
    occurs(move(Block,Location), T),
    block(Block),
    location(L),
    time(T).

:- occurs(move(Block,Location), T),
   not holds(clear(Location), T),
   block(Block),
   location(Location),
   time(T).

:- occurs(move(Block,Location), T),
   not holds(clear(Block), T),
   block(Block),
   location(Location),
   time(T).

-holds(on(Block,Location2), T) :-
    holds(on(Block,Location1), T),
    Location1 != Location2,
    block(Block),
    location(Location1),
    location(Location2),
    time(T).

-holds(clear(Block1), T) :-
    holds(on(Block2,Block1), T),
    block(Block1),
    block(Block2),
    time(T).

holds(clear(Table), T) :-
    table(Table),
    time(T).

holds(clear(Block), T) :-
    not -holds(clear(Block), T),
    block(Block),
    time(T).

% ============================
% INERTIA AXIOMS
% ============================

holds(Fluent, T + 1) :-
    holds(Fluent, T),
    not -holds(Fluent, T + 1),
    fluent(Fluent),
    time(T).

-holds(Fluent, T + 1) :-
    -holds(Fluent, T),
    not holds(Fluent, T + 1),
    fluent(Fluent),
    time(T).

% ============================
% INITIAL STATE
% ============================

holds(on(a,t), 0).
holds(on(b,t), 0).
holds(on(c,t), 0).
holds(on(d,t), 0).

% ============================
% GOAL SPECIFICATION
% ============================

goal(T) :-
	holds(on(d,c), T),
	holds(on(c,b), T),
	holds(on(b,a), T),
	holds(on(a,t), T),
	time(T).

done :-
	goal(T).

:- not done.

% ============================
% PLANNING MODULE
% ============================

1{occurs(Action,T) : action(Action)}1 :-
    not goal(T),
    time(T).

% ============================
% SOLVER DIRECTIVES
% ============================

#hide.
#show occurs(_,_).
\end{lstlisting}

\noindent Once again, using the clingo answer set solver we obtain the following single plan:
\begin{verbatim}
Answer: 1
occurs(move(d,c),2) occurs(move(c,b),1) occurs(move(b,a),0) 
SATISFIABLE

Models      : 1     
Time        : 0.000
  Prepare   : 0.000
  Prepro.   : 0.000
  Solving   : 0.000
\end{verbatim}

\subsubsection{Electrical Circuit}

We now turn our attention towards the representation of an electrical circuit domain. Such a domain is of interest due to the fact that there is essentially only a single action that an agent may perform, namely, the application of some input signals to the circuit. These signals must then be propagated throughout the entire circuit to obtain some output value.

Consider the electrical circuit shown in Figure~\ref{circuit}. Once a signal has been applied to inputs $1,2,3$, it must be propagated to the next level of the circuit within the same state. Static causal laws shine here.

\begin{figure}[htb]
    \centering
    \includegraphics[scale=0.50]{circuit}
    \caption{a simple electrical circuit}
    \label{circuit}
\end{figure}

\begin{lstlisting}[language=Prolog, caption=Electrical Circuit Domain Representation in A-Prolog, label=lst:asp-circuit]
% ============================
% OBJECTS
% ============================

time(0).

% ============================
% CIRCUIT STRUCTURE
% ============================

wire(1..6).
gate(1..3).
and(1).
inverter(2).
or(3).

% and gate has inputs 1 and 2

input_to(1,1..2).

% inverter has input 3

input_to(2,3).

% or gate has inputs 4 and 5

input_to(3,4..5).

% and gate has output 4

output_from(1,4).

% inverter has output 5

output_from(2,5).

% or gate has output 6

output_from(3,6).

% ============================
% GENERAL DESCRIPTION OF GATES
% ============================

h(val(OUTPUT_WIRE, 1), T) :- 
    output_from(GATE, OUTPUT_WIRE),
    and(GATE),
    input_to(GATE, INPUT1),
    input_to(GATE, INPUT2),
    INPUT1 != INPUT2,
    h(val(INPUT1, 1), T),
    h(val(INPUT2, 1), T),
    time(T).

h(val(OUTPUT_WIRE, 0), T) :- 
    output_from(GATE, OUTPUT_WIRE),
    and(GATE),
    input_to(GATE, INPUT),
    h(val(INPUT, 0), T),
    time(T).
    
h(val(OUTPUT_WIRE, 0), T) :- 
    output_from(GATE, OUTPUT_WIRE),
    or(GATE),
    input_to(GATE, INPUT1),
    input_to(GATE, INPUT2),
    INPUT1 != INPUT2,
    h(val(INPUT1, 0), T),
    h(val(INPUT2, 0), T),
    time(T).

h(val(OUTPUT_WIRE, 1), T) :- 
    output_from(GATE, OUTPUT_WIRE),
    or(GATE),
    input_to(GATE, INPUT),
    h(val(INPUT, 1), T),
    time(T).
    
h(val(OUTPUT_WIRE, 1), T) :-
    output_from(GATE, OUTPUT_WIRE),
    inverter(GATE),
    input_to(GATE, INPUT),
    h(val(INPUT, 0), T),
    time(T).

h(val(OUTPUT_WIRE, 0), T) :-
    output_from(GATE, OUTPUT_WIRE),
    inverter(GATE),
    input_to(GATE, INPUT),
    h(val(INPUT, 1), T),
    time(T).

% ============================
% INITIAL STATE
% ============================
    
h(val(1, 1), 0).
h(val(2, 0), 0).
h(val(3, 1), 0).

% ============================
% SOLVER DIRECTIVES
% ============================

#hide.
#show h(_,_).
\end{lstlisting}

\noindent Once again using clingo, we can see how the signal propagates across the various levels of the circuit:
\begin{verbatim}
Answer: 1
h(val(1,1),0) h(val(2,0),0) h(val(3,1),0) h(val(4,0),0) h(val(5,0),0) h(val(6,0),0) 
SATISFIABLE

Models      : 1     
Time        : 0.000
  Prepare   : 0.000
  Prepro.   : 0.000
  Solving   : 0.000
\end{verbatim}

\subsubsection{Towers of Hanoi}

The last domain we consider is the Towers of Hanoi domain. This domain was chosen due to the similarity of the PDDL and A-Prolog representations. The PDDL representation allows one to simulate in convenient ``lossless'' way the information stored in a static causal law concerning whether a disc or peg becomes clear. It is also an interesting planning problem in its own right.

\begin{lstlisting}[language=Prolog, caption=Towers of Hanoi Domain Representation in A-Prolog, label=lst:asp-hanoi]
% ============================
% OBJECTS
% ============================

#const n = 7.

time(0..n).

disc(1).
disc(2).
disc(3).

peg(p1).
peg(p2).
peg(p3).

location(X) :- peg(X).
location(X) :- disc(X).

% ============================
% FLUENTS
% ============================

fluent(on(Disc,Location)) :-
    disc(Disc),
    location(Location),
    Disc != Location.

fluent(clear(Location)) :-
    location(Location).

% ============================
% ACTIONS
% ============================

action(move(Disc,Source,Destination)) :-
    disc(Disc),
    location(Source),
    location(Destination),
    Source != Destination.

% ============================
% CAUSAL LAWS
% ============================

holds(on(Disc,Destination), T + 1) :-
    occurs(move(Disc,Source,Destination), T),
    disc(Disc),
    location(Source),
    location(Destination),
    time(T).

-holds(on(Disc,Source), T + 1) :-
    occurs(move(Disc,Source,Destination), T),
    disc(Disc),
    location(Source),
    location(Destination),
    time(T).

:- occurs(move(Disc,Source,Destination), T),
   not holds(on(Disc,Source), T),
   disc(Disc),
   location(Source),
   location(Destination),
   time(T).

:- occurs(move(Disc,Source,Destination), T),
   not holds(clear(Disc), T),
   disc(Disc),
   location(Source),
   location(Destination),
   time(T).

:- occurs(move(Disc,Source,Destination), T),
   not holds(clear(Destination), T),
   disc(Disc),
   location(Source),
   location(Destination),
   time(T).

:- occurs(move(Disc,Source,Destination), T),
   disc(Destination),
   Destination < Disc,
   disc(Disc),
   location(Source),
   location(Destination),
   time(T).

-holds(clear(Location), T) :-
    holds(on(Disc,Location), T),
    location(Location),
    disc(Disc),
    time(T).

holds(clear(Location), T) :-
    not -holds(clear(Location), T),
    location(Location),
    time(T).

% ============================
% INERTIA AXIOMS
% ============================

holds(Fluent, T + 1) :-
    holds(Fluent, T),
    not -holds(Fluent, T + 1),
    fluent(Fluent),
    time(T).

-holds(Fluent, T + 1) :-
    -holds(Fluent, T),
    not holds(Fluent, T + 1),
    fluent(Fluent),
    time(T).

% ============================
% INITIAL STATE
% ============================

holds(on(1,2), 0).
holds(on(2,3), 0).
holds(on(3,p1), 0).

% ============================
% GOAL SPECIFICATION
% ============================

goal(T) :-
    holds(on(1,2), T),
    holds(on(2,3), T),
    holds(on(3,p3), T),
    time(T).

done :-
    goal(T).

:- not done.

% ============================
% PLANNING MODULE
% ============================

1{occurs(Action,T) : action(Action)}1 :-
    not goal(T),
    time(T).

% ============================
% SOLVER DIRECTIVES
% ============================

#hide.
#show occurs(_,_).
\end{lstlisting}

\noindent Once again clingo gives us a plan for moving the disc to the destination peg:
\begin{verbatim}
Answer: 1
occurs(move(1,p1,2),6) occurs(move(2,p2,3),5) occurs(move(1,2,p1),4)
occurs(move(3,p1,p3),3) occurs(move(1,p3,2),2) occurs(move(2,3,p2),1)
occurs(move(1,2,p3),0) 
SATISFIABLE

Models      : 1+    
Time        : 0.030
  Prepare   : 0.020
  Prepro.   : 0.010
  Solving   : 0.000
\end{verbatim}

\section{Conclusions}

In keeping with Dijkstra's view of programming as the refinement of specification, we believe the approach taken by the knowledge representation and reasoning community to be more expressive. It has been shown to be capable of handling extremely robust domains such as the reaction control system of the space shuttle, \cite{usa}, and has been applied towards the task of \emph{conformant planning} as well \cite{conformant}. The central concept of reducing the task of planning to the computation of the answer sets of a logic program separates the quality and type of plans generated from the solver being used for their computation. The two become independent, and any improvements to the solving algorithm, have no effect on which plans are returned (as plans are simply the answer set of program). This is not the case in classical planning. In the classical planning approach the type and quality of plans produced are highly dependent on the type of solver being used. This makes it difficult to say what the actual \emph{meaning} of a PDDL domain representation actually is. It also makes it difficult to make general claims of the properties of PDDL domain description.

The two communities also use different notions of what a state is. In the classical planning community, a state is simply an interpretation of the fluents. In the knowledge representation community, states are interpretations that are closed with respect to all of the state constraints present in an action description. This has some profound consequences, particularly when coupled with many classical planners not supporting a feature known as domain axioms. Consider again Lin's Briefcase domain, and suppose we are in the state $\{open(l_{1}),open(l_{2}), open(b)\}$. Now suppose that we close one of the latches, $l_{1}$. Through the use of static causal laws, under the knowledge representation approach the successor state will be $\{\neg{open(l_{1})},open(l_{2}), \neg{open(b)}\}$. Under the classical planning approach however, we would have this $\{\neg{open(l_{1})},open(l_{2}), open(b)\}$ as a successor state, which violates our domain specification. Similar issues occur with the Electrical Circuit domain, where the interior elements have essentially undefined values until all of the requisite PDDL ``propagation'' actions have fired.

This lack of expressiveness on the part of PDDL is an intentional decision given that its express purpose was to serve as a vehicle for the planning competitions, and not as a knowledge representation language. We regret not having had the time to do some thorough benchmarking of some complex domains pitting the two approaches against each other. For certain domains, we believe that classical planners may have an edge, particularly those involving a considerable amount of numeric computation. For others however, we believe that given its impressive performance with regards to the shuttle \cite{usa}, and other complex domains, A-Prolog and the knowledge representation approach will prove to be quite competitive.

\begin{thebibliography}{2}

\bibitem{GL88}
Michael Gelfond and Vladimir Lifschitz.
The Stable Model Semantics for Logic Programming.
In Robert A.\, Kowalski and Kenneth Bowen, editors, Proceedings of the Fifth International Conference on Logic Programming, pages 1070{1080}, Cambridge, Massachusetts, 1988.
The MIT Press.

\bibitem{Baral03}
Chitta Baral.
Knowledge Representation, Reasoning, and Declarative Problem Solving.
Cambridge University Press, January 2003.

\bibitem{Bald2005}
Marcello Balduccini.
Answer Set Based Design of Highly Autonomous, Rational Agents.
PhD thesis, Texas Tech University, December 2005.

\bibitem{Shan97}
Murray Shanahan.
Solving the frame problem: A mathematical investigation of the commonsense law of inertia.
MIT Press, 1997.

\bibitem{Marek99}
Victor Marek and Mirek Truszczynski.
Stable models and an alternative logic programming paradigm.
The Logic Programming Paradigm, pp. 375–398, Springer, 1999.

\bibitem{Niemela99}
Ilkka Niemela.
Logic programming with stable model semantics as a constraint programming paradigm.
AMAI, 25(3,4), 1999.

\bibitem{clingo}
Martin Gebser, Roland Kaminski, et.\,al.\,
A User's Guide to gringo, clasp, clingo, and iclingo.
2010.

\bibitem{conformant}
Michael Gelfond and Ricardo Morales. 
Encoding Conformant Planning in A-Prolog. 
In DRT'04, 2004.

\bibitem{usa}
Marcello Balduccini, Michael Gelfond, Monica Nogueira, and Richard Watson.
Planning with the USA-Advisor. 
In 3rd International NASA Workshop on Planning and Scheduling for Space, Sep 2002.

\bibitem{Blum:1997vn}
A.~Blum and M.~Furst.
\newblock Fast planning through planning graph analysis.
\newblock {\em Artificial Intelligence}, 90(1-2):279--298, 1997.

\bibitem{Bonet:1997uq}
B.~Bonet, G.~Loernics, and H.~Geffner.
\newblock A robust and fast action selection mechanism for planning.
\newblock In {\em AAAI-97}, pages 714--719. MIT Press, 1997.

\bibitem{Bylander:1994kx}
T.~Bylander.
\newblock The computational complexity of propositional strips planning.
\newblock {\em Artificial Intelligence}, 69(1-2):165--204, 1994.

\bibitem{Hoffmann:2001fk}
J.~Hoffmann.
\newblock Ff: The fast-forward planning system.
\newblock {\em AI Magazine}, 22(3):57--62, 2001.

\bibitem{Thiebaux:2003ys}
S.~Thi{\'e}baux, J.~Hoffmann, and B.~Nebel.
\newblock In defense of pddl axioms.
\newblock {\em Artificial Intelligence}, 18:961--968, 2003.

\end{thebibliography}

\include{roles}

\end{document}